package main

import (
	"fmt"
)

// 写一个最简单的二分查找法

func main()  {
	nums :=[]int{12,213,323,43,4,232,31132,322,2,3233,323,32,3}

	nums =insert_sort(nums)
	fmt.Println(nums)
    idx :=binary_search(nums,31132)
	fmt.Println(idx)
	bianry_insert(&nums,12)
	fmt.Println(nums)

}

func insert_sort(arr []int) []int  {
	n :=len(arr)
	if n < 2 {
		return arr;
	}
	for i :=1;i<len(arr);i++{
        target := arr[i]
		l,h :=0,i-1
		for l<=h{
			mid := (l+h) /2 
			if arr[mid]== target {
				h = mid +1;
				l = mid+1;
			}else if arr[mid] < target{
				l = mid +1 
			}else{
				h = mid -1
			}
		}
		for j:=i;j>h+1;j--{
			// 元素后移
			arr[j] = arr[j-1] 
		}
		arr[h+1] = target
	}
	return arr;
}

// 用到append函数，指针
func bianry_insert(arr *[]int,target int) {
    if len(*arr) < 1 {
		*arr = append(*arr,target)
		return
	}
	l,mid,h:=0,0,len(*arr)-1

	for l<=h{
		mid =(l+h) /2
		if (*arr)[mid] == target{
			// 微调,保证插入时稳定性
			// h =mid
			// l =mid+1
			h = mid + 1
			l = mid + 1
		}else if (*arr)[mid] < target{
			l =mid+1
		}else{
			h = mid-1
		}
	}
	// 插入到mid位置，mid位置必定是合法的
	// 但是mid找到和未找到时，是mid-1还是mid位置有问题
	// 以mid为准有问题，可以考虑h
	//  分析边界条件，在相等时简单，不相等时，退出循环时，l=h+1
	// if arr[mid] < target , l -1 = h =mid ;else l =mid = h +1
	//  arr[l],arr[h],关系， arr[h] <= t < arr[l],稳定插入时，应该是h+1位置
	fmt.Printf("h:%d \n",h)
	// temp := append((*arr)[0:h+1],target)
	//  这是golang使用指针时,值覆盖了
	// *arr = append(temp,(*arr)[h+1:]...)
	*arr = append(*arr,0)
    for i:=len(*arr)-1;i>h+1;i--{
		(*arr)[i] = (*arr)[i-1]
	}
	(*arr)[h+1] = target;
}

func binary_search(arr []int,target int) int {
	n := len(arr)
	if n< 1{
		return -1;
	}
	l,h :=0,n-1
	// 要等号，不要会有边界问题
    for l <= h {
		mid := (l+h) /2 
		if  arr[mid] ==  target{
			return  mid
		}else if arr[mid] < target{
			l = mid+1
		}else{
			h = mid-1
		}
	}
	return -1
}


// 快速排序，它是递归的
func quick_sort(arr []int,l int,h int)  {
	if h-l <2{
		return
	}
	i,j,pivot :=l,h,arr[l]
	for i< j{
		for i< j && arr[j] >= pivot{
			j--
		}
		if(i<j){
			arr[i] = arr[j]
		}
		for i< j && arr[i] < pivot{
			i++
		}
		if i<j {
			arr[j] = arr[i]
		}
	}
	arr[i] = pivot;
	quick_sort(arr,l,i-1)
	quick_sort(arr,i+1,h)
}